/*
二分查找法的改进版
     与第一种方法不同点在于循环条件不能等于，当目标值小于中间值时，右指针直接赋值为中间值
     （相当于方法二的右指针不能指向已经比较过的元素）
 */

package com.diudiu.BinarySearch;

public class BinarySearch02 {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 6, 7, 9, 11, 24, 56, 66, 77, 88, 99, 121, 234, 345};
        int target = 56;
        int result = myBinarySearch02(array, target);
        System.out.println(result);
    }

    private static int myBinarySearch02(int[] array, int target) {
        //计算数组长度
        int len = array.length;
        //左边指针
        int left = 0;
        //右边指针
        int right = len;
        while (left < right) {
            //中间变量
            //注：>>>无符号右移，忽略符号位，空位都以0补齐，避免用 / 造成失误
            int mid = (left + right) >>> 1;
            //目标值小于中间值
            if (target < array[mid]) {
                //右指针赋值为中间值减一
                right = mid;
            } else if (target > array[mid]) {
                //左指针赋值为中间值加一
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

}
